package com.gxc.string;

/**
 * 给定一个字符串str，如果可以在str的任意位置添加字符，
 * 请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。
 * [举例]
 * str="ABA”。str本身就是回文串，不需要添加字符，所以返回“ABA”。
 * str="AB”。可以在A之前添加B’，使str整体都是回文串，故可以返回”BAB”。
 * 也可以在B之后添加'A'，使str整体都是回文串，故也可以返回”ABA"。
 * 总之，只要添加的字符数最少，返回其中一种结果即可。
 *
 * 解法一：
 * i 从头开始遍历  j 从尾开始遍历
 * 如果str[i]!=str[j] 则在i位置之前插入str[j]字符，i 不变，j--
 * 直到i=j
 *
 * 解法二：
 * dp[i][j] 表示 str i j 位置上 达成回文字符串的最少添加
 * str[i]==str[j] dp[i][j] = dp[i+1][i-1];
 * str[i]!=str[j] dp[i][j] = min(dp[i+1][j] , dp[i][i-1]) + 1;
 * 然后根据dp 转回 string
 */
public class AddPalindrome {

    public static void main(String[] args) {
        String str = "ABA";
        System.out.println(str.substring(1));

        System.out.println(process(str));

        str = "AB";
        System.out.println(process(str));

        str = "ABCDBA";
        System.out.println(process(str));

        System.out.println(process2(str));
    }

    public static String process(String str) {
        if (str == null || str.length()<2) return str;

        int i = 0;
        int j = str.length()-1;

        char[] chars = str.toCharArray();
        StringBuffer buffer = new StringBuffer();
        while (i!=j) {
            if (chars[i] != chars[j]) {
                buffer.append(chars[j]);
            } else {
                buffer.append(chars[i]);
                i++;
            }
            j--;
        }
        buffer.append(str.substring(j));
        return buffer.toString();
    }

    public static String process2(String str) {
        int[][] dp = dp(str);
        int min = dp[0][str.length()-1];
        char[] res = new char[str.length() + min];

        int i = 0;
        int j = str.length()-1;

        char[] chars = str.toCharArray();
        int resi = 0;
        int resj = res.length-1;
        while (i <= j) {
            if (chars[i] == chars[j]) {
                res[resi++] = chars[i++];
                res[resj--] = chars[j--];
            } else if (dp[i+1][j] < dp[i][j-1]){
                res[resi++] = chars[i];
                res[resj--] = chars[i++];
            } else {
                res[resi++] = chars[j];
                res[resj--] = chars[j--];
            }
        }
        return String.valueOf(res);
    }

    public static int[][] dp(String str){
        int[][] dp = new int[str.length()][str.length()];

        char[] chars = str.toCharArray();
        for (int j = 1; j < dp.length; j++) {
            dp[j-1][j] = chars[j-1] == chars[j] ?0:1;
            for (int i = j-2; i >= 0; i--) {
                if (chars[i] == chars[j]) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]) + 1;
                }
            }
        }

        return dp;
    }
}
